<!--
   /index.html
   Copyright 2012 Erik Strelzoff

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
-->
<html>
<head>
<!-- TBI: Investigate using RequireJS or other module manager -->
<!-- Douglas Crockford's JSON-js package -->
<script type="text/javascript" src="json2.js"></script>
<script type="text/javascript" src="jquery.js"></script>
<!-- js_bintrees package for red-black tree  https://github.com/vadimg/js_bintrees -->
<script type="text/javascript" src="rbtree.js"></script>
<link rel="stylesheet" href="hexmap.css">
</head>
<div id="hexmap"></div>

<!-- templates -->
<div id="templates" class="hidden">
  <h1>Templates</h1>

  <div class="tiles water">
    <img src="water.png" width="72" height="72"/>
  </div>
  <div class="tiles desert">
    <img src="desert.png" width="72" height="72"/>
  </div>
  <div class="tiles forest">
    <img src="forest.png" width="72" height="72"/>
  </div>
  <div class="tiles mountain">
    <img src="mountain.png" width="72" height="72"/>
  </div>
  <div class="piece red_square">
	<img src="red_square.jpg" width="25" height="25"/>
  </div>
</div>

<div id="controlPanel">
	<button id="moveButton" type="button" value="move">Move</button>
</div>

<script>

var servletURL = "/magelord/MageLordServlet";

// Milliseconds to wait between server polls.  Server may changed this.
var pollInterval = 5000;

// Margin of offset pixels from the top for map placement
var top_margin = 5;

// Map object
// - Tile array
// - Piece array
// - selected:  Currently selected unit or tile
var map = {
	typeName: "map",
	tiles: [],
	pieces: [],
	// Current thing selected (tile or piece).
	selected: null,
	path: null,
	select: function (mapElement) {
		if (this.selected != null) {
			// TBI:
			//this.deselect(this.selected);
		}
		highlight(mapElement);
		this.selected = mapElement;
	},
	deselect: function (mapElement) {
		dehighlight(mapElement);
		if (mapElement === this.selected) {
			this.selected = null;
		}
	}};

var moveMode = false;

$("#moveButton").bind("click", function(event) {
	if ((map.selected != null) &&
		(map.selected.typeName == "tile")) {
		moveMode = true;
	}
});

// Setup recursive polling.
// TBI:  If there is a single failure, polling will stop.  Maybe it should auto-recover.
//
/*
(function poll(){
   setTimeout(function(){
		console.log("Polling...");
		// Maybe this should be pulled into it's own 'refresh' function.  
		// Then the user could request refresh themselves.  But we would probably
		// want to avoid two simultanous or near-simultaneous refreshes.
		$.getJSON( servletURL, { request: "getState" }, function(data) {
			console.log("Poll success");
			// Server may return multiple commands.  
			// Loop through each one and apply it.
			var commands = data.commands;
			for (i = 0; i < commands.length; i++) {
				var command = commands[i];
				// Call the command function requested
				commandMap[command.name](command);
			}

			// Setup the next poll recursively
			poll();
		});
  }, pollInterval);
})();
*/

var commandMap = {
	setPollInterval: function(command) {
		// Make sure it is a number and has a minimum length of 1 second.
		if (command.interval === "number" && command.interval >= 1000) {
			pollInterval = command.interval;
		} else {
			console.log("setPollInterval: ignoring: " + command.interval);
		}
	},
	movePiece: function(command) {
		var piece = map.pieces[command.pieceId];
		var tile = map.tiles[command.tilex][command.tiley];
			
		if (piece != null && tile != null) {
			tile.placePiece(piece);
		} else {
			if (piece == null) console.log("Could not find piece: " + command.pieceId);
			if (tile == null) console.log("Could not find tile at: " + command.tilex + "," + command.tiley);
		}
	},
};

$(document).ready(function(){
	getMap();
});

function getMap() {
	var getMapRequest = {
		request: "loadMap",
		id: "1"
	};

	console.log("Sending servlet request");
	
	// Ajax error handling.  Doesn't give a lot of useful info.
	$(document).ajaxError( function(event, jqXHR, ajaxSettings, thrownError) {
		console.log("ajaxError Handler triggered");
		console.log("event: " + JSON.stringify(event));
		console.log("jqXHR: " + JSON.stringify(jqXHR));
		console.log("ajaxSettings: " + JSON.stringify(ajaxSettings));
		console.log("Error: " + JSON.stringify(thrownError));
	});
	
	// Retrieve the map 
	$.getJSON( servletURL, getMapRequest, function(data, textStatus, jqXHR) {
		console.log("Received response.  textStatus " + textStatus);
		
		// Populate the hexmap from provided data.
		map.tiles = populate(data.hexmap);
		
		// Place a piece on a hex.
		// Pick a tile based on coordinates.  Or maybe just the first one.
		// Place the piece on the hex.
		/*
		piece = newPiece("red_square");
		map.tiles[0][0].placePiece(piece);
		map.pieces[0] = piece;
		
		piece = newPiece("red_square");
		map.tiles[1][2].placePiece(piece);
		map.pieces[1] = piece;
		*/
	} );
}
   
/*
  Given a 2d String array of hex tile names
  iterate through it and position the named tiles in 
  their proper places in the hexmap div
*/
function populate(hexmap) {
  var tileArray = [];
  for (var x = 0; x < hexmap.length; x++) {
    var column = hexmap[x];
	tileArray[x] = [];
    for (var y = 0; y < column.length; y++) {
      
      // clone the tile and place it
	  var tile = newTile(column[y], x, y);
	  tile.position();
	  tile.m_image.appendTo($('#hexmap'));
      tileArray[x][y] = tile;

	  // Associate the new tile to the neighbors around it.
	  
	  // Up-down association
	  if (y > 0) {
		var upTile = tileArray[x][y - 1];
		tile.m_neighbors[5] = upTile;
		upTile.m_neighbors[2] = tile;
	  }
	  
	  // Left-right association.
	  var offset = x % 2;
	  if (x > 0) {
	    var leftTile = tileArray[x - 1][y];
		tile.m_neighbors[3 + offset] = leftTile;
		leftTile.m_neighbors[0 + offset] = tile;

		if (offset == 0 && y > 0) {
			// Up-left, down-right association
			var otherTile = tileArray[x - 1][y - 1];
			tile.m_neighbors[4] = otherTile;
			otherTile.m_neighbors[1] = tile;
		}
		
		// If offset is 1, we are an up hex column, so need to do
		// the down-left, up right association
		if (offset == 1 && y < column.length - 1) {
			var otherTile = tileArray[x - 1][y + 1];
			tile.m_neighbors[3] = otherTile;
			otherTile.m_neighbors[0] = tile;
		}
	  }
    }
  }
  

  return tileArray;
}

function newPiece(name) {
	var piece = {
		typeName: "piece",
		m_image: $("." + name, "#templates").children().clone(),
		m_name: name,
		m_tile: null
	};
	// Add click handler
	piece.m_image.bind("click", function(event) {
		map.select(piece);
	});
	
	return piece;
}

/**
 * Construct a new Tile object.
 */
function newTile(name, x, y) {
	var tile = {
		typeName: "tile",
		terrain: name,
		m_image: $("." + name, "#templates").children().clone(),
		m_x: x,
		m_y: y,
		// Consistent hex coordinates.  
		// Used to measure real distance over the map.
		m_hx: x,
		// Here we shift the Y axis.  Runs down to the right instead 
		// of straight up-down.
		// Every other increment of x requires an extra y increment.
		m_hy: y + Math.ceil(x / 2),
		// Key identifying this tile.  Defined below: tile.m_hx + "," + tile.m_hy;
		m_key: "",
		// Neighbors
		m_neighbors: [],
		m_xpos: 0,
		m_ypos: 0,
		// m_terrain: ?
		
		/*
		  Place the tile based on row and column data 
		  attached to the element set
		*/
		position: function() {
			// We store the row and column in the tile for 
			// use in the tooltip stuff
			//this.data({"row": row, "column": column});
			
			var tile_width = this.m_image.attr("width");
			var tile_height = this.m_image.attr("height");
			
			var y_offset = tile_height / 2;
			var x_offset = tile_width / 4;
			
			this.m_xpos = 0 + (this.m_x * (tile_width - x_offset));
			this.m_ypos = 0 + (this.m_y * tile_height) + y_offset;
			 
			// Add margin offset to the top.
			this.m_ypos += top_margin; 
			
			if (this.m_x % 2 == 0) {
			  this.m_ypos -= y_offset;
			}
			
			var style = {"position": "absolute", 
						 "top": this.m_ypos, "left": this.m_xpos};
			
			var ret = this.m_image.css(style);
			return ret;
		  },
		  placePiece: function(piece) {
			var xpos = this.m_xpos + 25;
			var ypos = this.m_ypos + 25;
			
			var css_properties = {"position": "absolute", "top": ypos, "left": xpos};
			
			if (piece.m_tile == null) {
				piece.m_image.css(css_properties);
				// Is 'appendTo' the right method if the piece is moved
				piece.m_image.appendTo($('#hexmap'));
			} else {
				piece.m_image.animate(css_properties);
			}
			
			piece.m_tile = this;
		  },
		  // Determine the simple distance in hex steps from another tile.
		  distance: function(tile) {
			var xdelta = tile.m_hx - this.m_hx;
			var ydelta = tile.m_hy - this.m_hy;
			// Delta-delta.  The differece of the differences.
			var ddelta = xdelta - ydelta;
			
			// Take the absolute value of the greatest of the above.
			var dist = Math.max(Math.max(Math.abs(xdelta), Math.abs(ydelta)), Math.abs(ddelta));
			return dist;
		  },
		  /**
		   * Print out the coordinates of this hex
		   */
		  toString: function() {
			return "hex: (" + this.m_hx + ", " + this.m_hy + ")";
		  }
	};	  
      tile.m_image.bind("click", function(event) {
		var units = null;
		if (moveMode) {
			if (map.selected == null) {
				map.select(tile);
			} else if ((map.selected != null) &&
					   (map.selected.typeName == "tile")) {
				var path = findPath(units, map.selected, tile);
				
				// Remove highlighting from previous path.
				if (map.path != null) { dehighlight(map.path); }
				highlight(path);
				// Remember the path.
				map.path = path;
				moveMode = false;
			}
		} else {
			console.log("Tile clicked: " + tile);
			if (map.selected != null) {
				map.deselect(map.selected);
			}
			// Remove highlighting from previous path.
			if (map.path != null) { dehighlight(map.path); }
			map.select(tile);
		}
	  });

	tile.m_key = tile.m_hx + "," + tile.m_hy;
	  
	return tile;
} 

/********************************************************/
/*** Path Finding Code  */
/********************************************************/
function findPath(units, start_tile, goal_tile) {
	var before = millis();
	var nodes_considered = 0;
	// Implementation of the A* pathfinding algorithm.
	// Thanks to Amit Patel for his outstanding explanation of how this works:
	// http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
	//
	// Three structures
	// 1.  Open Set.  Set of tiles being examined.  
	//     Implemented as an object with string-form coordinates mapping to tiles.
	// 2.  Ordered tile list of the open set.
	//     Implemented as a red-black tree.  Descending rank (best node last).
	// 3.  Closed set.
	//     Implemented as # 1.
	start_node = makeNode(start_tile);
	
	// Set the initial cost from start to end.
	var start_distance = start_tile.distance(goal_tile);
	
	// Starting gvalue is zero (cost to move to ourselves is zero)
	start_node.gvalue = 0;
	// Starting rank is gvalue + basic heuristic (distance to goal)
	start_node.rank = start_distance;
	
	var openSet = {};
	openSet[start_node.key] = start_node;
	// Our sorted form of the open set.  A red-black tree.
	var openTree = new RBTree(
		// Search node comparison function
		function(node1, node2) {
			// Simple test.  If they are the same, then they are the same
			if (node1.key === node2.key) return 0;
			
			var comp = node2.rank - node1.rank;
			if (comp != 0) return comp;
			
			// Nodes of equal rank should hopefully be rare if the heuristic is done
			// right.  But we need to handle it somehow anyway so that two different
			// nodes are never considered the same in terms of comparison.			
			
			// Do simple string comparison of the keys.
			// We already know they are different.
			comp = node1.key > node2.key ? 1 : node1.key < node2.key ? -1 : 0;
			
			return comp;
		} );
	openTree.insert(start_node);
	var closedSet = {};
	var debug = false;
	
	while (true) {
		var current_node = openTree.max();
		if (debug) console.log("Considering top-ranked: " + current_node.tile + " rank: " + current_node.rank);
		
		// If lowest ranked node is the goal, then we are done.
		if (current_node.tile === goal_tile) {
			if (debug) console.log("Found goal!");
			break;
		}
		nodes_considered++;
		
		// Add current to closed
		closedSet[current_node.key] = current_node;
		// And remove it from open.
		openSet[current_node.key] = null;
		var removeResult = openTree.remove(current_node);
		if (debug) {
			if (removeResult != null) {
				console.log("Remove top-ranked successful: " + removeResult);
			} else {
				console.log("Remove top-ranked failed!  Tried to remove: " + current_node );
			}
		}
		
		// Consider neighbors
		$.each(current_node.tile.m_neighbors, function(index, neighbor) {
			// Check boundaries.
			if (typeof(neighbor) !== "undefined") {
		
				// cost = g(current) + movementcost(current, neighbor)
				//var neighbor_distance = neighbor.distance(goal_tile);
				var cost = current_node.gvalue + moveCost(units, neighbor);
				// Ignore the cost of moving into the goal tile.
				if (neighbor === goal_tile) cost = 0;
				
				// if neighbor in OPEN and cost less than g(neighbor):
				if ((openSet[neighbor.m_key] != null) &&
					(cost < openSet[neighbor.m_key].gvalue)) {
					if (debug) console.log("Removing node from open: " + openSet[neighbor.m_key].tile);
					// Remove neighbor from openTree and openSet
					removeResult = openTree.remove(openSet[neighbor.m_key]);
					if (debug) {
						if (removeResult != null) {
							console.log("Remove successful: " + removeResult);
						} else {
							console.log("Remove failed!  Tried to remove: " + openSet[neighbor.m_key]);
						}
					}
					openSet[neighbor.m_key] = null;
				}
				
				// if neighbor in CLOSED and cost less than g(neighbor):
				if ((closedSet[neighbor.m_key] != null) &&
					(cost < closedSet[neighbor.m_key].gvalue)) {
					if (debug) console.log("Removing node from closed: " + closedSet[neighbor.m_key].tile);
					closedSet[neighbor.m_key] = null;
				}
				
				// if neighbor not in OPEN and neighbor not in CLOSED:
				if ((openSet[neighbor.m_key] == null) &&
					(closedSet[neighbor.m_key] == null)) {
					var neighbor_node = makeNode(neighbor);
					neighbor_node.gvalue = cost;
					// set priority queue rank to g(neighbor) + h(neighbor)
					neighbor_node.rank = neighbor_node.gvalue + pathHeuristic(start_tile, neighbor, goal_tile);
					neighbor_node.parent = current_node;
					openSet[neighbor.m_key] = neighbor_node;
					openTree.insert(neighbor_node);
					
					if (debug) console.log("Adding neighbor to open: " + neighbor + " rank: " + neighbor_node.rank);
				}
				
				
			}
		});
	} // End while loop
	
	// reconstruct reverse path from goal to start by following parent pointers
	var pathList = [];
	var current_node = openTree.max();
	do {
		pathList.push(current_node.tile);
		current_node = current_node.parent;
	} while (current_node != null);
	// Reverse the path we constructed.
	pathList.reverse();
	
	if (debug) {
		$.each(pathList, function(index, value) {
			console.log("Step: " + index + ": " + value);
		});
	}
	
	var after = millis();
	console.log("findPath elapsed: " + (after - before) + " ms.  nodes considered: " + nodes_considered + " path length: " + pathList.length);
	
	return pathList;
} // End findPath

function makeNode(around_tile) {
	return {
		tile: around_tile,
		key: around_tile.m_key,
		parent: null,
		// Value of the g(n) function for this node.
		gvalue: 0,
		rank: 0,
		toString: function() {
			return this.tile + " Node. rank: " + this.rank;
		}
	};
}

// TBI:  Define terrain cost per unit type.
var terrainCost = {};
terrainCost["forest"] = 1;
terrainCost["water"] = 10;
terrainCost["mountain"] = 3;
terrainCost["desert"] = 2;
function moveCost(units, tile) {
	var cost = terrainCost[tile.terrain];
	if (typeof(cost) != "undefined") return cost;
	
	console.log("moveCost: Unknown terrain type: " + tile.terrain);
	return 1;
}

/**
 * Heuristic function for path finding.  Uses distance between the 
 * current tile considered and the goal, while giving a preference to
 * tiles which form a path closer to a straight line from start to goal.
 */
function pathHeuristic(start_tile, current_tile, goal_tile) {

	var dist = current_tile.distance(goal_tile);
	
	// Over very short distances, skip the cross product adjustment below.
	if (dist < 2) return dist;

	// Compute two vectors and their cross product.  The value will
	// be large if they don't line up and so will adjust the return value
	// of the heuristic.
	var dx1 = current_tile.m_hx - goal_tile.m_hx;
	var dy1 = current_tile.m_hy - goal_tile.m_hy;
	var dx2 = start_tile.m_hx - goal_tile.m_hx;
	var dy2 = start_tile.m_hy - goal_tile.m_hy;
	
	var cross = Math.abs(dx1*dy2 - dx2*dy1);
	
	var heuristic = cross*0.001 + dist;
	
	// Tie-breaking nudge.  Try to prevent nodes with equal rank.
	heuristic *= 1.0001;
	
	return heuristic;
}

/********************************************************/
/*** End Path Finding Code  */
/********************************************************/

function highlight(mapElement) {
	setOpacity(mapElement, ".7");
}
function dehighlight(mapElement) {
	setOpacity(mapElement, "1.0");
}
function setOpacity(mapElement, opacity) {
	if (typeof(mapElement.typeName) !== "undefined") {
		// Single map element
		mapElement.m_image.css({"opacity": opacity});
	} else {
		$.each(mapElement, function(index, value) { 
			value.m_image.css({"opacity": opacity});
		});
	}
}

// Array Remove - By John Resig (MIT Licensed)
Array.prototype.remove = function(from, to) {
  var rest = this.slice((to || from) + 1 || this.length);
  this.length = from < 0 ? this.length + from : from;
  return this.push.apply(this, rest);
};

// Find and remove the first instance of an item from an array
Array.prototype.removeItem = function(object) {
	for (i = 0; i < this.length; i++) {
		if (this[i] === object) {
			return this.remove(i);
		}
	}
	console.log("Array.removeItem: Failed to find object to remove");
	return this;
};

// Add string comparison function for red-black tree management
String.prototype.compare = function(str) {
	return this > str ? 1 : this < str ? -1 : 0;
};

/**
 * Number of milliseconds since the epoch.
 */
function millis() {
	return new Date().getTime();
}

</script>
</html>